package arithmetic;

import java.util.zip.CRC32;

/**
 * Created by AJie on 2019/3/29
 * Function :152  乘机最大连续子序列 ，动态规划
 *
 * 给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。
 *
 * 示例 1:
 *
 * 输入: [2,3,-2,4]
 * 输出: 6
 * 解释: 子数组 [2,3] 有最大乘积 6。
 *
 * 152. 乘积最大子数组
 * 链接：https://leetcode-cn.com/problems/maximum-product-subarray
 *
 */
public class A_28_MaxProductSubarray {
    public static void main(String[] args) {

    }

    public int max = Integer.MIN_VALUE;

    //动态规划 OK
    public int maxProduct(int[] nums) {
        int res = nums[0];//临时缓存，所有 出现过的最大值
        int dpn[] = new int[2];
        dpn[0]= dpn[1] = nums[0];// 初始化，最大值，最小值。
        for (int i = 1; i < nums.length; i++) {
            int current = nums[i];

            int max = dpn[0] * current;
            int min = dpn[1] * current;

            dpn[0] = Math.max(Math.max(max,min),current);
            dpn[1] = Math.min(Math.min(max,min),current);

            res = Math.max(res,dpn[0]);
        }

        return res;
    }

    //TODO  不成功待优化
    public int maxProduct1(int[] nums) {
        recursion(0, nums, true, 0);
        recursion(0, nums, false, 0);
        return max;
    }

    //TODO  不成功待优化
    public void recursion(int index, int[] nums, boolean isChoice, int res) {
        if (index >= nums.length) return;
        int current = nums[index];
        if (isChoice) {
            if (max == Integer.MIN_VALUE && res == 0) {
                res = current;
            }else {
                res = current * res;
            }
            if (res >max){
                max = res;
            }
        }
        index++;
        recursion(index,nums,true,res);
        recursion(index,nums,false,res);
    }




}
